package logic;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;
import java.util.Stack;

import data.AlgorithmInput;
import data.ClusteringGraphData;
import data.ClusteringInput;
import data.Data;
import data.GraphData;

public class ClusteringAlgorithm extends Algorithm{

	int[] luns;


	public GraphData compute(AlgorithmInput input, Data data) {
		ClusteringInput clusteringInput = (ClusteringInput)input;
		luns = data.getLUNs();
		double[][] lunVectors = new double[luns.length][];
		double[] vecSum = new double[luns.length];

		//computing the vectors, and vector sums (X~) for all of the LUNs
		for (int i=0; i<luns.length; i++){
			lunVectors[i] = data.getLUNVector(luns[i], clusteringInput.get_priorityParameter(), clusteringInput.get_dateStart(), clusteringInput.get_dateEnd());		//getting the vector
			vecSum[i] = 0;
			for (int j=0; j<lunVectors[i].length; j++){
				vecSum[i] = vecSum[i] + lunVectors[i][j];								//computing vector sums
			}
			vecSum[i] = vecSum[i]/(double)(vecSum.length);	//TODO - should it be number of luns or number of integers in the vector ???
		}

		ClusteringGraphNode[] nodes = new ClusteringGraphNode[luns.length];
		Set<ClusteringGraphNode> clusteringGraphNodes = new HashSet<ClusteringGraphNode>();
		for (int i=0; i<luns.length; i++){
			nodes[i] = new ClusteringGraphNode(luns[i]+"");
			clusteringGraphNodes.add(nodes[i]);
		}

		Set<ClusteringGraphEdge> clusteringGraphEdges = new HashSet<ClusteringGraphEdge>();

		for (int i=0; i<luns.length; i++){
//			if (i % 7 == 0) System.out.println("xxxxxxxxxxxxxxxx");
			for (int j=i+1; j<luns.length; j++){
				double sigmaXY = 0;
				double sigmaX = 0;
				double sigmaY = 0;
				double xT = vecSum[i];	//(x~)
				double yT = vecSum[j];	//(y~)
				for (int k=0; k< Math.max(lunVectors[i].length, lunVectors[j].length); k++){
					double xVal;
					double yVal;
					if (k<lunVectors[i].length){
						xVal = lunVectors[i][k];
					} else {
						xVal = 0;
					}
					if (k<lunVectors[j].length){
						yVal = lunVectors[j][k];
					} else {
						yVal = 0;
					}
					sigmaXY = sigmaXY + (xVal - xT)*(yVal - yT);
					sigmaX = sigmaX + (xVal - xT)*(xVal - xT);
					sigmaY = sigmaY + (yVal - yT)*(yVal - yT);
				}

				double cosTheta = sigmaXY/(Math.sqrt(sigmaX)*Math.sqrt(sigmaY));
//				System.out.println(cosTheta);
				double theta = Math.acos(cosTheta);
		//		System.out.println("{" + i + ", " + j + "} - " + theta);
//				System.out.println(theta);


				ClusteringGraphEdge ed = new ClusteringGraphEdge(nodes[i], nodes[j], theta);
//				if (i/7==j/7){
//					System.out.print(("" + theta).substring(0, 5) + " ");
//				}
//				if (i%7 == j%7 && i%7==1){
//					System.out.println("i="+i + ", j=" + j + " : " + theta);
//				}
				clusteringGraphEdges.add(ed);
			}
//			System.out.println();
		}
		return computeClusters(clusteringGraphEdges, clusteringGraphNodes, clusteringInput.get_numClusters());
	}

	//TODO - an easy way to improve the algorithm is to build an effective database to sort it out
	private ClusteringGraphData computeClusters(Set<ClusteringGraphEdge> edges, Set<ClusteringGraphNode> nodes, int numClusters){
		//edges - contains all of the edges between nodes that are in L
		//nodes - contains all of the nodes that are in L

		while (nodes.size() > numClusters){			//continue until we have the wanted number of clusters
			ClusteringGraphEdge bestEdge = null;	//find the minimal pair I,J such that Dij is minimal - using the edges
			double minD = Double.MAX_VALUE;
			for (ClusteringGraphEdge ed: edges){
//				System.out.println(ed.angle + " " + ed.lunID1.computeR(nodes) + " " + ed.lunID2.computeR(nodes));
//original algorithm - double Dij = ed.angle - (ed.lunID1.computeR(nodes) + ed.lunID2.computeR(nodes));
				double Dij = ed.angle;
//				System.out.println(Dij +" " + minD);
				if (Dij < minD) {
					minD = Dij;
					bestEdge = ed;
				}
			}

			ClusteringGraphNode nodeI = bestEdge.lunID1;
			ClusteringGraphNode nodeJ = bestEdge.lunID2;

//			System.out.println(nodeI.lunID + ", " + nodeJ.lunID + " - " + bestEdge.angle);

			ClusteringGraphNode nodeK = new ClusteringGraphNode("{"+nodeI.lunID+", " + nodeJ.lunID +"}"); //TODO make a unique number

			double dij = bestEdge.angle;
			System.out.println(nodeK.lunID + " - " + dij);

			//compute dkm for all of the nodes in L, and insert the new edges to the list
			for (ClusteringGraphNode nodeM: nodes) if (nodeM!=nodeI && nodeM!=nodeJ){
				double dkm = 0.5*(nodeI.getEdge(nodeM).angle + nodeJ.getEdge(nodeM).angle - dij);
				ClusteringGraphEdge edgeKM = new ClusteringGraphEdge(nodeK, nodeM, dkm);
				edges.add(edgeKM);
			}

			//compute the edges between I,J and K, note that we compute R here - it must be done BEFORE removing I and J from the node list
			double dik = 0.5*(dij+nodeI.computeR(nodes)-nodeJ.computeR(nodes));
			double djk = 0.5*(dij-dik);
			new ClusteringGraphEdge(nodeK, nodeI, dik);		//add an edge between K and I
			new ClusteringGraphEdge(nodeK, nodeJ, djk);		//add an edge between K and J

			//removing the edges related to I and J from the edge list
			edges.removeAll(nodeI.edges);
			edges.removeAll(nodeJ.edges);

			//remove I and J from the node list
			nodes.remove(nodeI);
			nodes.remove(nodeJ);
			//add K to the node list
			nodes.add(nodeK);

			nodeK.addChild(nodeI);
			nodeK.addChild(nodeJ);
		}
		return getClusters(nodes);
	}

	private ClusteringGraphData getClusters(Set<ClusteringGraphNode> nodes){
		List<List<String> > clusters = new LinkedList<List<String> >();
		for (ClusteringGraphNode n: nodes){
			List<String> cluster = new LinkedList<String>();
			Stack<ClusteringGraphNode> q = new Stack<ClusteringGraphNode>();
			q.add(n);
			while (!q.isEmpty()){
				ClusteringGraphNode tempNode = q.pop();
				if (tempNode.kids.isEmpty()){
					cluster.add(tempNode.lunID);
				} else {
					for (ClusteringGraphNode tempNode2: tempNode.kids){
						q.push(tempNode2);
					}
				}
			}
			clusters.add(cluster);
		}

		return new ClusteringGraphData(clusters);
	}

	private static class ClusteringGraphNode{
		String lunID;
		Set<ClusteringGraphEdge> edges;
		Set<ClusteringGraphNode> kids;

		public ClusteringGraphNode(String lunID) {
			this.lunID = lunID;
			this.edges = new HashSet<ClusteringGraphEdge>();
			this.kids = new HashSet<ClusteringGraphNode>();
		}

		public void addEdge(ClusteringGraphEdge ed){
			edges.add(ed);
		}

		public void addChild(ClusteringGraphNode n){
			kids.add(n);
		}

		public double computeR(Set<ClusteringGraphNode> nodes){
			double dSigma = 0;
			for (ClusteringGraphEdge ed: edges){
				ClusteringGraphNode otherNode = (ed.lunID1==this ? ed.lunID2 : ed.lunID1);
				if (nodes.contains(otherNode)){
					dSigma = dSigma + ed.angle;
				}
			}
			return dSigma/(double)(nodes.size()-2);
		}

		public ClusteringGraphEdge getEdge(ClusteringGraphNode n){
			for (ClusteringGraphEdge ed: edges){
				if (ed.lunID1==n || ed.lunID2==n){
					return ed;
				}
			}
			return null;
		}

	}

	private static class ClusteringGraphEdge{
		ClusteringGraphNode lunID1;
		ClusteringGraphNode lunID2;
		double angle;
		public ClusteringGraphEdge(ClusteringGraphNode lunID1, ClusteringGraphNode lunID2, double angle) {
			this.lunID1 = lunID1;
			this.lunID2 = lunID2;
			this.angle = angle;
			lunID1.addEdge(this);
			lunID2.addEdge(this);
		}
	}

	//TODO MY REMARKS
	// something is wrong with the formula to compute the cos of the angle, the numbers come out bigger than 1
	// vectors like [5,5,5] and [8,8,8] which supposed to be the same have an angle
}
